11161. Помочь моему брату (II)

Числа Фибоначчи определяются следующим рекуррентным соотношением:

f (1) = 1, f (2) = 1,

f (n > 2) = f (n – 1) + f (n – 2)

Неотрицательные числа записываются на бумаге. В i-ой строке записывается f(i) чисел, i = 0, 1, 2, … . Для чисел каждой строки вычисляется медиана:

0 Медиана: 0

1 Медиана: 1

2 3 Медиана: 2

4 5 6 Медиана: 5

7 8 9 10 11 Медиана: 9

12 13 14 15 16 17 18 19 Медиана: 15

Для заданного номера строки следует найти медиану чисел, стоящих в ней. Известно, что

медиана последовательности =

Вход. Каждое входное число содержит номер строки n (1 £ n £ 1500). Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого значения n вывести номер теста и медиану n-ой строки, как показано в примере. Выходное значение для любого теста содержит не более 350 цифр.

Пример входа

1

2

3

4

5

6

0

Пример выхода

Set 1:

0

Set 2:

1

Set 3:

2

Set 4:

5

Set 5:

9

Set 6:

15

РЕШЕНИЕ

длинная арифметика + числа Фибоначчи

Анализ алгоритма

Воспользуемся классом BigInteger. Генерируем все 1500 чисел Фибоначчи, вычисляем значения медиан всех строк и запоминаем их в массиве median. Для каждого входного значения n выводим соответствующее значение медианы из массива median.

Реализация алгоритма

Объявим текущие переменные типа BigInteger и массив median, в котором вычислим значения медиан всех строк.

BigInteger s, a, b, temp;

BigInteger median[1501];

Реализуем метод Even в классе BigInteger, возвращающий 1, если число четно.

class BigInteger

{

. . .

int Even(void)

{

return 1 - m[0] % 2;

}

};

Установим a = 1, b = 1. Медиана нулевой строки равна 0.

a = b = BigInteger(1);

s = median[0] = BigInteger(0);

Находим значения медиан всех строк и заносим их в массив median. Генерируем все 1500 чисел Фибоначчи (a = F_i+1, b = F_i). Значение s в начале i - ой итерации цикла равно последнему числу (i – 1) - ой строки (поэтому перед циклом установлено s = 0). i - ая строка содержит a чисел, равных s + 1, s + 2, …, s + a. Медиана i - ой строки вычисляется по формуле, приведенной в условии.

for(i = 1; i <= 1500; i++)

{

if (a.Even()) median[i] = s + a / 2;

else median[i] = s + (a + 1) / 2;

s = s + a;

temp = b; b = a; a = b + temp;

}

Читаем входное значение n и выводим значение медианы n -ой строки, которое находится в median[n – 1].

while(scanf("%d",&n),n)

{

printf("Set %d:\n",test),median[n-1].print();

test++;

}